package it.conv;

import static java.lang.Math.*;

public class Decoder {
	
	private int in = 1;
	private int out;
	private int lung_canale;
	private int M;
	private int[][] g;
	
	// numero degli stati = 2^in*(K - 1) = 2^in*m in = 1
	private int L;
	/*
	 * Piccola degradazione delle performance raggiunta limitando la profondità
	 * del traliccio a M * 5
	 */
	private int MAX_PROF;
	//Parametro K del codificatore convoluzionale
	private int KAPPA;
	//Per il rate in/out è 2^in (in questo caso con rate 1/2 allora 2^1)
	private int IN;
	
	private int[] tabellaQuant;
	
	//Ingresso + Shift Register del codificatore
	private int[] memoria;
	// Mappaggio stato corrente/prossimo - ingresso
	private int[][] input;
	// Restituisce le uscite del codificatore convoluzionale
	private int[][] output;
	// Per lo stato corrente, restituisce il prossimo ingresso dato
	private int[][] mapStati;
	// Metrica degli errori accumulati
	private int[][] metricaAcc;
	// Tabella cronologica degli stati
	private int[][] cronologiaStati;
	// Lista finale delle sequenze degli stati
	private int[] sequenzaStati;
	
	//Matrice d'ingresso
	private int[] matriceOutputCanale;
	
	//Vettore per registrare l'uscita binaria del codificatore
	private int[] outputBin;
	//Vettore per registrare l'uscita di prova del codificatore
	private int[] outputBranch;
	
	public Decoder(double[] canale, int m, int[][] p, int out, int l) {
		
		M = m;
		g = p;
		this.out = out;
		lung_canale = (l + M - 1) * this.out;
		L = 1 << (in * (M - 1));
		MAX_PROF = (l < M * 5 - 3) ? lung_canale / this.out : M * 5;
		KAPPA = M - 1;
		IN = 1 << in;
		
//		DEBUG
//		System.out.println("DECODER\nN.Stati = " + L);
//		System.out.println("Profondità traliccio = " + MAX_PROF);
//		System.out.println("M = " + M);
//		for (int i = 0; i < g.length; i++) {
//			System.out.print("Polinomio g" + i + " = [ ");
//			for (int j = 0; j < g[i].length; j++)
//				System.out.print( g[i][j] + " ");
//			System.out.println("]");
//		}
		
		//Inizializzazione delle strutture dati
		tabellaQuant = new int[256];
		
		input = new int[L][L];
		output = new int[L][IN];
		mapStati = new int [L][IN];
		cronologiaStati = new int[L][MAX_PROF + 1];
		sequenzaStati = new int[MAX_PROF + 1];
		metricaAcc = new int[L][IN];
		
		memoria = new int[M];
		outputBranch = new int[IN];
		outputBin = new int[IN];
		
		matriceOutputCanale = new int[lung_canale];
		
		for (int i = 0; i < L; i++) {
			
			int j;
			for (j = 0; j < L; j++)
				input[i][j] = 0;
			
			for (j = 0; j < IN; j++) {
				
				mapStati[i][j] = 0;
				output[i][j] = 0;
				
			}
			
			for (j = 0; j <= MAX_PROF; j++)
				cronologiaStati[i][j] = 0;
			
			//Inizializzazione metricaAcc[x][0] = 0
			metricaAcc[i][0] = 0;
			//Impostando metricaAcc[x][1] a INT_MAX, non c'è bisogno di flag
			metricaAcc[i][1] = Integer.MAX_VALUE;
				
		}
		
	    /*
	     * Generazione della matrice di transizione degli stati, matrice di uscita, e la matrice di ingresso
	     * - la matrice di ingresso mostra come i bit del codificatore FEC passano al prossimo stato
	     * - la matrice di transizione mostra il prossimo stato dato quello corrente e il bit di input
	     * - la matrice di output mostra i bit di output del codificatore FEC dati gli stati del codificatore
	     *   correnti ipotizzati e i bit di ingresso del codificatore
	     * Verranno comparati ai simboli ricevuti attualmente per determinare la metrica per il corrispondente
	     * ramo del traliccio
	     */
		for (int i = 0; i < L; i++)
			for (int j = 0; j < IN; j++) {
				
				int proxStato = proxStato(i, j);
				input[i][proxStato] = j;
				
				int k;
				/* 
				 * Calcola le uscite del codificatore convoluzionale dati i numeri degli stati correnti e il
	             * valore di ingresso
	             */
				for (k = 0; k < outputBranch.length; k++)
					outputBranch[k] = 0;
				
				for (k = 0; k < M; k++)
					for (int ix = 0; ix < outputBranch.length; ix++)
						outputBranch[ix] ^= memoria[k] & g[ix][k];
				
				//Prossimo stato, dato lo stato corrente e l'input
				mapStati[i][j] = proxStato;
				//Uscita in decimale, dato lo stato corrente e l'input
				output[i][j] = bin2deci(outputBranch);
				
			}
		/*
		 * Inizializzazione quantizzatore non adattativo
		 * inizializzaQuant();
		 */
		//Inizializzazione quantizzatore adattativo
		inizializzaQuantAdattativo();
		
		/*
		 * Quantizza il canale di uscita -- converte un float in un intero
	     * matriceOutputCanale = riforma(canale[], N, ConvApp.LUN_CANALE)
	     */
		for (int t = 0; t < lung_canale; t += this.out)
			for (int i = 0; i < out; i++)
				matriceOutputCanale[(t + i * lung_canale) / this.out] = 
					quantSoftDecision(canale[t + i]);
		
	}
	
	/* 
	 * Inizio della decodifica delle uscite del canale con attraversamento in avanti del traliccio!
	 * Il termine solo dopo il flusso di codifica dei bit.
	 */
	public int[] decode() {
		
		int[] matriceDecodificata = new int[lung_canale / out - M + 1];		
		int x, xx, hh, h = 0, puntCS, colCS, ultimo, metrica;
		
	    /* 
	     * Ora si ricalibra il canale di uscita tale da avere n righe, e n/2 colonne dove ogni riga
	     * corrisponde ad un simbolo di canale per un bit dato e ogni colonna corrisponde ad un bit
	     * codificato
	     */
		int l = lung_canale / out;
		for (int t = 0; t < l - KAPPA; t++){
			
			int step = 1;
			
			if (t <= KAPPA)
		           /*
		            * Si assume di partire con zeri, così da calcolare i percorsi con stati con tutti
		            * valori zero
		            */
				step = 1 << (KAPPA - t * in);
			
	        /* 
	         * Si usa l'array cronologico come un buffer circolare così non si deve spostare tutto a
	         * sinistra dopo che ogni bit venga processato, significa aver bisogno di un puntatore
	         * appropriato
	         * Imposta il puntatore dell'array cronologico dello stato per il periodo t
	         */
			puntCS = (t + 1) % (MAX_PROF + 1);
			
			//Ripete per ogni stato possibile
			for (int i = 0; i < L; i += step)
				//Ripete per ogni possibile n-upla delle uscite del codificatore convoluzionale
				for (int j = 0; j < IN; j++) {
					
					metrica = 0;
					
					/*
					 * Calcola la metrica di taglio per il simbolo di canale, e somma per tutti i
					 * simboli di canale nelle n-uple delle uscite del codificatore convoluzionale
					 */
					deci2bin(output[i][j], outputBin);
                    
					/* 
					 * Calcola la metrica di taglio per il simbolo di canale, e somma per tutti i
					 * simboli di canale nelle n-uple delle uscite del codificatore convoluzionale
					 */
					for (int k = 0; k < out; k++)
						metrica = metrica + metricaSoft((matriceOutputCanale[k * l + t]),
									outputBin[k]);
					
					/* 
					 * Ora sceglie il percorso superstite -- l'unico con la più piccola
					 * metrica di errore accumulata
					 */
					if (metricaAcc[mapStati[i][j]][1] > metricaAcc[i][0] + metrica) {
						
						//Salva il valore di metrica accumulata per lo stato superstite
						metricaAcc[mapStati[i][j]][1] = metricaAcc[i][0] + metrica;
						/* 
						 * Aggiorna l'array cronologico dello stato con il numero dello stato
						 * del percorso superstite
						 */
						cronologiaStati[mapStati[i][j]][puntCS] = i;
						
					}
					
				}
			
			/* 
			 * Per tutte le righe di accum_err_metric, sposta la colonna 2 sulla colonna 1 e
			 * segna la colonna 2
	         */
			for (int i = 0; i < L; i++) {
				
				metricaAcc[i][0] = metricaAcc[i][1];
				metricaAcc[i][1] = Integer.MAX_VALUE;
				
			}
			
			//Ora parte con la risalita, se il traliccio è stato riempito
			if (t >= MAX_PROF - 1) {
				
				//Inizializza il vettore sequenzaStati
				for (int i = 0; i <= MAX_PROF; i++)
					sequenzaStati[i] = 0;
				
				/* 
				 * Cerca l'elemento di cronologiaStati con la metrica di errore accumalata minore
				 * 
	             * Finchè gli stati esterni vengono raggiunti da cicli di zeri e uno
	             * relativamente improbabili, cerca da cima a fondo all'interno del traliccio
	             */
				x = Integer.MAX_VALUE;
			 	
				for (int i = 0; i < (L / 2); i++) {
					
					if (metricaAcc[i][0] < metricaAcc[L - 1 - i][0]) {
						
						xx = metricaAcc[i][0];
						hh = i;
						
					} else {
						
						xx = metricaAcc[L - 1 - i][0];
						hh = L - 1 - i;
						
					}
					
					if (xx < x) {
						
						x = xx;
						h = hh;
						
					}
					
				}
				
				//Ora prende il punto di partenza della risalita
				sequenzaStati[MAX_PROF] = h;
				
				/*
				 * Ora lavora al contrario dalla fine del traliccio fino al più vecchio stato
				 * all'interno di esso per selezionare il percorso ottimo. Lo scopo di ciò è di
				 * determinare la sequenza di stati più simile alla base del codificatore
				 * sul quale ha ricevuto i simboli di canale.
				 */
				for (int i = MAX_PROF; i > 0; i--) {
					
					colCS = i + (puntCS - MAX_PROF);
					if (colCS < 0)
						colCS = colCS + MAX_PROF + 1;
					sequenzaStati[i - 1] = cronologiaStati[sequenzaStati[i]][colCS];
					
				}
				
				/*
				 * Ora capisce a quale sequenza di ingresso corrisponde la sequanza dello stato
				 * nel percorso ottimale
				 */
				matriceDecodificata[t - MAX_PROF + 1] = input[sequenzaStati[0]][sequenzaStati[1]];
				
			}
			
		}
		
		//Ora decodifica i bit del flusso del canale di uscita del decodificatore
		for (int t = l - KAPPA; t < l; t++) {
			
			//Imposta il puntatore dell'array cronologico dello stato per questo periodo t
			puntCS = (t + 1) % (MAX_PROF + 1);
			
			/*
			 * Non c'è bisogno di considerare gli stati dove l'ingresso è stato un 1, così come
			 * determinare quale sia il numero di stati più alti possibile dove l'ingresso è stato 0
			 */
			ultimo = L / (1 << t - l + KAPPA);
			
			//Ripete  per ogni possibile stato
			for (int i = 0; i < ultimo; i++) {
				
				metrica = 0;
				deci2bin(output[i][0], outputBin);
				
				/*
				 * Calcola la metrica di taglio per i bit di canale, e somma per tutti i
                 * bit di canale nelle n-uple delle uscite del codificatore convoluzionale
                 */
				for (int k = 0; k < IN; k++)
					metrica = metrica + metricaSoft(matriceOutputCanale[k * l + t],
							outputBin[k]);
				
				/*
				 * Ora sceglie il percorso superstite -- l'unico con la metrica
				 * totale più bassa...
				 */
				if (metricaAcc[mapStati[i][0]][1] > metricaAcc[i][0] + metrica) {
					
					//Salva il valore della matrica dello stato per lo stato superstite
					metricaAcc[mapStati[i][0]][1] = metricaAcc[i][0] + metrica;
					/*
					 * Aggiorna l'array cronologico dello stato con il numero dello stato del
                     * percorso superstite
					 */
					cronologiaStati[mapStati[i][0]][puntCS] = i;
					
				}
				
			}
			
			//Per ogni riga di accum_err_metric, scambia la colonna 1 e 2
			for (int i = 0; i < L; i++) {
				
				metricaAcc[i][0] = metricaAcc[i][1];
				metricaAcc[i][1] = Integer.MAX_VALUE;
				
			}
			
			//Ora parte con la risalita, se i >= depth_of_trellis - 1
			if (t >= MAX_PROF - 1) {
				
				//Inizializza il vettore sequenzaStati
				for (int i = 0; i < MAX_PROF; i++)
					sequenzaStati[i] = 0;
				
				/*
				 * Trova l'elemento di cronologiaStati con la minima metrica di
                 * errore accumulata
				 */
				x = metricaAcc[0][0];
				h = 0;
				for (int i = 1; i < ultimo; i++)
					if (metricaAcc[i][0] < x) {
						
						x = metricaAcc[i][0];
						h = i;
						
					}
				
				sequenzaStati[MAX_PROF] = h;
				
				/* 
				 * Ora lavora al contrario dalla fine del traliccio fino al più vecchio stato
				 * all'interno di esso per selezionare il percorso ottimo. Lo scopo di ciò è
				 * di determinare la sequenza di stati più simile alla base del codificatore
				 * sul quale ha ricevuto i simboli di canale.
				 */
				for (int i = MAX_PROF; i > 0; i--) {
					
					colCS = i + (puntCS - MAX_PROF);
					if (colCS < 0)
						colCS = colCS + MAX_PROF + 1;
					sequenzaStati[i - 1] = cronologiaStati[sequenzaStati[i]][colCS];
					
				}
				
				/*
				 * Ora capisce a quale sequenza di ingresso corrisponde la sequenza dello stato
				 * nel percorso ottimale
				 */
				matriceDecodificata[t - MAX_PROF + 1] = input[sequenzaStati[0]][sequenzaStati[1]];
				
			}
			
		}
		
		//Aggiorna la matrice decodificata
		for (int i = 1; i < MAX_PROF - KAPPA; i++)
			matriceDecodificata[l - MAX_PROF + i] = input[sequenzaStati[i]][sequenzaStati[i + 1]];
		
		return matriceDecodificata;
		
	}
	// Inizializza un quantizzatore soft-decision a 3 bit ottimizzato per circa 4 dB Eb/No
	private void inizializzaQuant() {
		
		int i;
		
	    for (i = -128; i < -31; i++)
	        tabellaQuant[i + 128] = 7;
	    for (i = -31; i < -21; i++)
	    	tabellaQuant[i + 128] = 6;
	    for (i = -21; i < -11; i++)
	    	tabellaQuant[i + 128] = 5;
	    for (i = -11; i < 0; i++)
	    	tabellaQuant[i + 128] = 4;
	    for (i = 0; i < 11; i++)
	    	tabellaQuant[i + 128] = 3;
	    for (i = 11; i < 21; i++)
	    	tabellaQuant[i + 128] = 2;
	    for (i = 21; i < 31; i++)
	    	tabellaQuant[i + 128] = 1;
	    for (i = 31; i < 128; i++)
	    	tabellaQuant[i + 128] = 0;
		
	}
	
	//Inizializza un quantizatore che si adatta a Es/N0
	private void inizializzaQuantAdattativo() {
		
		int i, d = (int) (32 * 0.5 * DataGenerator.var);
		
		for (i = -128; i < (-3 * d); i++)
			tabellaQuant[i + 128] = 7;
		for (i = (-3 * d); i < (-2 * d); i++)
			tabellaQuant[i + 128] = 6;
		for (i = (-2 * d); i < -d; i++)
			tabellaQuant[i + 128] = 5;
		for (i = -d; i < 0; i++)
			tabellaQuant[i + 128] = 4;
		for (i = 0; i < d; i++)
			tabellaQuant[i + 128] = 3;
		for (i = d; i < (2 * d); i++)
			tabellaQuant[i + 128] = 2;
		for (i = (2 * d); i < (3 * d); i++)
			tabellaQuant[i + 128] = 1;
		for (i = (3 * d); i < 128; i++)
			tabellaQuant[i + 128] = 0;
		
	}
	
	/*
	 * Questo quantizzatore assume che il valore medio di channel_symbol sia +/- 1,
     * e lo traduce in un intero il cui valore medio è +/- 32 per indirizzare la
     * lookup table "quantizer_table". La protezione per l'overflow è inclusa.
	 */
	private int quantSoftDecision(double simbolo) {
		
		int x = (int) (32 * simbolo);
		if (x < -128)
			x = -128;
		else if (x > 127)
			x = 127;
		
		return (tabellaQuant[x + 128]);
		
	}
	
	//Questa metrica è basata su un algoritmo creato da Michelson e Levesque.
	private int metricaSoft(int dato, int ipotesi) {
		return abs(dato - (7 * ipotesi));
	}
	
	/*
	 * Questa funzione calcola lo stato successivo del codificatore convoluzionale, dato
     * lo stato corrente e i dati di ingresso. Inoltre calcola i contenuti della memoria
     * del codificatore convoluzionale.
	 */
	private int proxStato(int statoCorr, int input) {
		
		//Valore decimale dello stato successivo
		int proxStato;
		//Valore binario dello stato corrente
		int[] statoBin = new int[M - 1];
		//Valore binario dello stato successivo
		int[] proxStatoBin = new int[M - 1];
		
		//Converte il valore decimale del numero dello stato corrente in binario
		deci2bin(statoCorr,statoBin);
		
		/*
		 * Dato l'ingresso e il numero dello stato corrente, calcola il numero
		 * dello stato successivo
		 */
		proxStatoBin[0] = input;
		for (int i = 1; i < statoBin.length; i++)
			proxStatoBin[i] = statoBin[i - 1];
		
		//Converte il valore binario del numero dello stato successivo in decimale
		proxStato = bin2deci(proxStatoBin);
		
		//memoria[] sono gli ingressi ai sommatori modulo 2 del codificatore
		memoria[0] = input;
		for (int i = 1; i < statoBin.length + 1; i++)
			memoria[i] = statoBin[i - 1];
		
		return proxStato;
		
	}
	
	/* 
	 * Questa funzione converte un numero decimale in un numero binario, memorizzato
	 * come un vettore che inizia con l'MSB, avente un numero predeterminato di bit
	 * eventualmente riempito con zeri
	 */
	public static void deci2bin(int d, int[] b) {
		
		for (int i = 0; i < b.length; i++)
			b[i] = 0;
		
		b[b.length - 1] = d & 0x01;
		for (int i = b.length - 2; i >= 0; i--) {
			d = d >> 1;
			b[i] = d & 0x01;
		}
		
	}
	
	/*
	 * Questa funzione converte un numero binario avente un numero specifico di
     * bit con il corrispondente valore decimale
	 */
	public static int bin2deci(int[] b) {
		
		int d = 0;
		for (int i = 0; i < b.length; i++)
			d += b[i] << (b.length - i - 1);
		
		return d;
		
	}

}
